Euler の定理
$ a^{\varphi(n)}\overset n\equiv 1
$ \varphi(n)
を
$ n
未満の
$ n
と違いに素な自然数の個数とする
Euler 関数
$ n
が素数の時は
$ \varphi(n)=n-1
より
Fermat の小定理
に一致
ちなみに
$ a^{-1}\overset n\equiv a^{\varphi(n)-1}
だが、
Euler 関数
を求める計算量が
$ \Omicron(\sqrt n)
なので速い計算はできない
素因数分解
がネックになっている